// 封装优先级队列 ES5写法
function PriorityQueue() {
  var items = [];

  // 封装一个新的构造函数, 用于保存元素和元素的优先级
  function QueueElement(element, priority) {
    this.element = element;
    this.priority = priority;
  }

  // 添加元素的方法
  this.enqueue = function (element, priority) {
    // 1.根据传入的元素, 创建新的QueueElement
    var queueElement = new QueueElement(element, priority);

    // 2.如果是空队列，直接放入
    if (this.isEmpty()) {
      items.push(queueElement);
      return;
    }

    // 3.获取传入元素应该在正确的位置
    if (queueElement.priority < items[0].priority) {
      // 3.1：如果传入元素权重最高（数字最小），放在队列第一位
      items.unshift(queueElement);
    } else if (queueElement.priority > items[items.length - 1].priority) {
      // 3.2：如果传入元素权重最低（数字最大），放在队列最后一位
      items.push(queueElement);
    } else {
      // 3.3：传入的元素权重处于中间位置，找到合适的位置并插入
      var start = 0;
      var end = items.length - 1;
      while (start < end - 1) {
        var middle = Math.floor((start + end) / 2);
        var current = items[middle].priority;
        if (current > queueElement.priority) {
          end = middle;
        } else if (current <= queueElement.priority) {
          start = middle;
        }
      }
      items.splice(start, 0, queueElement);
    }
  };

  // 删除元素的方法
  this.dequeue = function () {
    return items.shift();
  };

  // 获取前端的元素
  this.front = function () {
    return items[0];
  };

  // 查看元素是否为空
  this.isEmpty = function () {
    return items.length == 0;
  };

  // 获取元素的个数
  this.size = function () {
    return items.length;
  };
}
// test
// 创建优先级队列对象
// var pQueue = new PriorityQueue();

// // 添加元素
// pQueue.enqueue("abc", 10);
// pQueue.enqueue("cba", 5);
// pQueue.enqueue("nba", 12);
// pQueue.enqueue("mba", 3);

// // 遍历所有的元素
// var size = pQueue.size();
// for (var i = 0; i < size; i++) {
//   var item = pQueue.dequeue();
//   console.log(item.element + "----" + item.priority);
// }
/*
mba----3
cba----5
abc----10
nba----12
*/

// -------------------------------------------
// -------------------------------------------
// ---------------ES6 class写法---------------
// -------------------------------------------
// -------------------------------------------

class QueueEle {
  constructor(value, priority) {
    this.val = value;
    this.pri = priority;
  }
}

class PriQueue {
  constructor() {
    this.item = [];
  }
  // 添加元素的方法
  enqueue(element, priority) {
    // 1.根据传入的元素, 创建新的元素
    let newElement = new QueueEle(element, priority);
    // 2.如果是空队列，直接放入
    if (this.item.length === 0) {
      this.item.push(newElement);
      return;
    }
    // 3.获取传入元素应该在正确的位置
    if (newElement.priority < this.item[0].priority) {
      // 3.1：如果传入元素权重最高（数字最小），放在队列第一位
      this.item.unshift(newElement);
    } else if (newElement.priority > this.item[this.item.length - 1].priority) {
      // 3.2：如果传入元素权重最低（数字最大），放在队列最后一位
      this.items.push(newElement);
    } else {
      // 3.3：传入的元素权重处于中间位置，找到合适的位置并插入
      // 二分查找合适的位置
      let start = 0;
      let end = this.item.length - 1;
      while (start < end - 1) {
        let middle = Math.floor((start + end) / 2);
        let current = this.item[middle].priority;
        if (current > newElement.priority) {
          end = middle;
        } else if (current <= newElement.priority) {
          start = middle;
        }
      }
      this.item.splice(start, 0, newElement);
    }
  }
  // 删除元素的方法
  dequeue() {
    this.item.shift(0);
  }
  // 获取前端的元素
  front() {
    return this.item[0];
  }
  // 查看元素是否为空
  isEmpty() {
    return this.item.length === 0;
  }
  // 获取元素的个数
  size() {
    return this.item.length;
  }
}

let ins = new PriQueue();
ins.enqueue("a", 111);
ins.enqueue("b", 11);
ins.enqueue("c", 1);
console.log(ins);
